§4.4 Non-Atomic Congestion Games
finite set of populations $\tilde N$ consisting of a continuum of players $[0,d_i]$
finite set of resources $R$ with non-neg., non-decr., cont. resource costs $c_r: \IRnn \to \IRnn$
sets of strategies $S_i \subseteq \set{0,1}^R$
set of strategy profiles of population $i$ : $X_i \coloneqq \set{x_i \in \IRnn^{S_i} \sMid \sum_{s_i \in S_i}x_{is_i} = d_i}$
set of strategy profiles : $X \coloneqq \prod_{i \in \tilde N}X_i$
$\ell: X \to \IRnn^R, x \mapsto (\ell_r(x)) \coloneqq \bigl(\sum_{i \in \tilde N}\sum_{s_i \in S_i:\, r \in R(s_i)}x_{is_i}\bigr)$ load/congestion vector
private cost of players of population $i$ using strategy $s_i \in S_i$ under strategy profile $x \in X$:
\[\pi_{is_i}(x) \coloneqq \sum_{r \in R(s_i)}c_r(\ell_r(x))\]
⤳ social cost $C(x) \coloneqq \sum_{i \in \tilde N}\sum_{s_i \in S_i}\pi_{is_i}(x)\cdot x_{is_i} \class{tempstep a}{\data{tempstep-from=22}{= \sum_{r \in R}c_r(\ell_r(x))\cdot\ell_r(x)}}$
⤳ $x \in X$ Wardrop equilibrium $\coloniff \forall i \in \tilde N\, \forall s_i, s'_i \in S_i:$ $x_{is_i} \gt 0$ $\,\implies \pi_{is_i}(x) \leq \pi_{is'_i}(x)$
For (atomic) congestion game $G=(N,S,\pi)$: (pure) Nash equilibrium $\coloniff \forall i \in N \, \forall s'_i \in S_i: \pi_i(s) \leq \pi_i(s'_i,s_{-i})$
\tilde N = [1]
d_1 = 1
\small\color{black} o
\small\color{black} v
\small\color{black} w
\small\color{black} d
\small\color{black}z \mapsto z
\small\color{black}z \mapsto 1
\small\color{black}z \mapsto 0
\small\color{black}z \mapsto 1
\small\color{black}z \mapsto z
\small\color{var(--blue)}1/2
\small\color{var(--green)}1/2
\small\color{var(--red)}1
$R(s)$
$\color{var(--blue)}\set{ov,vd}$
$\color{var(--green)}\set{ow,wd}$
$\color{var(--red)}\set{ov,vw,vd}$
$x$
$1/2$
$1/2$
$0$
$\pi_{s}(x)$
$3/2$
$3/2$
$1$
$x'$
$0$
$0$
$1$
$\pi_{s}(x')$
$2$
$2$
$2$
Lem. 4.51: $x \in X$ WE $\implies \exists k_i \in \IRnn: \forall s_i \in S_i: \pi_{is_i}(x) \begin{cases}= k_i, &\text{if } x_{is_i} \gt 0 \\ \geq k_i, &\text{else}\end{cases}$
Thm. 4.52: For any $x \in X$ the following are equivalent
$x$ is a Wardrop equilibrium
$\forall y \in X: \sum_{r \in R}c_r(\ell_r(x))\cdot(\ell_r(y)-\ell_r(x)) \geq 0$ mmmm "variational inequality"
$x \in \argmin_{z \in X} \Phi(z) \coloneqq \sum_{r \in R}\int_0^{\ell_r(z)}c_r(t)\diff t$mmmmmm "optimum of potential"
Thm. 4.53: For any non-atomic congestion game
There exists a Wardrop equilibrium
$\forall x,y \in X$ WE $\implies \forall r \in R: c_r(\ell_r(x)) = c_r(\ell_r(y))$
If all $c_r$ are strictly increasing then, additionally,
$\forall x,y \in X$ WE $\implies \forall r \in R: \ell_r(x) = \ell_r(y)$
$G=(N,S,\pi)$ unw. (atomic) congestion game Wardrop equilibrium $\coloniff \forall i \in N, s_i' \in S_I:$
For (atomic) congestion game $G=(N,S,\pi)$: (pure) Nash equilibrium $\coloniff \forall i \in N \, \forall s'_i \in S_i: \pi_i(s) \leq \pi_i(s'_i,s_{-i})$
Lem. 4.55: In unweighted atomic congestion games with non-decreasing, separable resource cost fcts every WE is also a PNE .